package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 6. Z 字形变换
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 *
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 *
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 *
 * 请你实现这个将字符串进行指定行数变换的函数：
 *
 * string convert(string s, int numRows);
 *
 *
 * 示例 1：
 *
 * 输入：s = "PAYPALISHIRING", numRows = 3
 * 输出："PAHNAPLSIIGYIR"
 * 示例 2：
 * 输入：s = "PAYPALISHIRING", numRows = 4
 * 输出："PINALSIGYAHRPI"
 * 解释：
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 * 示例 3：
 *
 * 输入：s = "A", numRows = 1
 * 输出："A"
 *
 * //https://leetcode-cn.com/problems/zigzag-conversion/
 */
public class Zigzag6 {





    private static int yu(int x,int y){
        return x%y==0?y:x%y;
    }

    private static int chu(int x,int y){
        return x%y==0?x/y-1:x/y;
    }


    public static String  convert(String s, int numRows) {
        // 两种特殊情况先枚举下,提高速度
        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        if (numRows == 2) {
            // 先取所有奇数位,在取所有偶数位
            int i = 0;
            while (i < s.length()) {
                sb.append(s.indexOf(i++));
            }
            i = 1;
            while (i < s.length()) {
                sb.append(s.indexOf(i++));
            }
            return sb.toString();
        }
        // 常规解法
        // 1.生成z字型的二维坐标, 数组.
        //0_0,1_0,2_0,

        // 2.根据上述最后一个坐标生成 容器二维数组, 空白处就是char默认字符,
        int[] index = getIndex(s.length(), numRows);
        char[][] arr = new char[numRows][index[0] + 1];

        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            int[] index1 = getIndex(i + 1, numRows);
            arr[index1[1]][index1[0]] = c;
        }
        // 3.依次横向打印数组,默认字符就忽略.
        char[] result = new  char[s.length()];
        int l =0;
        for (int i = 0; i < arr.length; i++) {
            char[] c = arr[i];
            for (int j = 0; j < c.length; j++) {
                char c1 = c[j];
                if (c1 != '\0') {
                    result[l++] = c1;
                }
            }
        }
        return new String(result);
    }

    /**
     *
     * @param i  第i个数
     * @param n 行数>2
     * @return
     */
    private static int[] getIndex(int i, int n) {
        int x;
        int y;

        // 一次循环的布长
        int step = (2 * n - 2);
        // ?
        int p = (chu(i,step) +1) * (n - 1) - n + 2;
        // 循环后的位置
        int turns = yu(i,2 * n - 2);
        // 相同
        if (turns <= n) {
            x = p;
            y = turns;
        } else {
            x = p +(turns-n);
            y = 2 * n - turns;
        }
        return new int[] {x - 1, y - 1};
    }




    public static void main(String[] args) {
        //System.out.println(Arrays.toString(getIndex(6, 4)));
       /* for (int i = 1; i <= 20; i++) {
            System.out.println(Arrays.toString(getIndex(i, 2)));
        }*/

        //输入：s = "PAYPALISHIRING", numRows = 3
        //输出："PAHNAPLSIIGYIR"
        System.out.println(convert("PAYPALISHIRING",3));
        //输入：s = "PAYPALISHIRING", numRows = 4
        //输出："PINALSIGYAHRPI"
        System.out.println(convert("PAYPALISHIRING",4));
        //输入：s = "A", numRows = 1

        System.out.println(2%2);

        //输出："PAHNAPLSIIGYIR"
        System.out.println(convert2("PAYPALISHIRING",3));
        //输入：s = "PAYPALISHIRING", numRows = 4
        //输出："PINALSIGYAHRPI"
        System.out.println(convert2("PAYPALISHIRING",4));


        System.out.println(convert3("PAYPALISHIRING",3));
        System.out.println(convert3("PAYPALISHIRING",4));
    }

    /**
     *  第二种方法，直接打进数组里  模拟打印
     *  执行用时：
     * 6 ms Java 提交中击败了 77.84%
     * 内存消耗： 39.1 MB 45.69%
     * @param s
     * @param numRows
     */
    public static String convert2(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        if (numRows == 2) {
            StringBuilder sb =new StringBuilder(numRows);
            // 先取所有奇数位,在取所有偶数位
            int i = 0;
            while (i < s.length()) {
                sb.append(s.charAt(i++));
            }
            i = 1;
            while (i < s.length()) {
                sb.append(s.charAt(i++));
            }
            return sb.toString();
        }

        StringBuilder[] sba = new StringBuilder[numRows];
        // 初始化下
        for (int i = 0; i < numRows; i++) {
            sba[i] = new StringBuilder();
        }
        int currLine = 0;
        boolean shouldPlus = true;
        for (int i = 0; i <  s.length(); i++) {
            sba[currLine].append(s.charAt(i));
            if (currLine == numRows - 1) {
                shouldPlus = false;
            }
            if (currLine == 0) {
                shouldPlus = true;
            }
            // 偶数下降
            if (shouldPlus) {
                currLine++;
            } else {
                currLine--;
            }
            // System.out.println(currLine);
           /* //
            if(curruntArray<numRows){
                curruntArray++;
            }
            i++;*/
        }
        for (int i = 1; i < sba.length; i++) {
            sba[0].append(sba[i]);
        }
        return sba[0].toString();
    }

    /**
     *  模拟打印的优化  	通过	6 ms	38.8 MB	Java
     * @param s
     * @param numRows
     * @return
     */
    public static String convert3(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder[] sba = new StringBuilder[numRows];
        // 初始化下
        for (int i = 0; i < numRows; i++) {
            sba[i] = new StringBuilder();
        }
        char[] chars = s.toCharArray();
        int cycle = 2*numRows -2;
        for (int i = 0; i < chars.length; i++) {
            // 0121 0121 012  4
            // 012321 012321  6 周期  2n-2
            // i%numRows 0 1 2 0 1
            // i/numRows 0 0 0 1 1 1 2 2 2
            // i/numRows%2 000 111 000
            int j = i % cycle;
            if(j>cycle/2){
                //System.out.println(cycle-j);
                sba[cycle-j].append(chars[i]);

            }else {
               // System.out.println(j);
                sba[j].append(chars[i]);
            }

        }
        for (int i = 1; i < sba.length; i++) {
            sba[0].append(sba[i]);
        }
        return sba[0].toString();
    }

    public  String convert4(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder[] sba = new StringBuilder[numRows];

        for (int i = 0; i < numRows; i++) {
            sba[i] = new StringBuilder();
        }
        char[] chars = s.toCharArray();
        int cycle = 2*numRows -2;
        for (int i = 0; i < chars.length; i++) {

            int j = i % cycle;
            if(j>cycle/2){
                sba[cycle-j].append(chars[i]);

            }else {
                sba[j].append(chars[i]);
            }
        }
        for (int i = 1; i < sba.length; i++) {
            sba[0].append(sba[i]);
        }
        return sba[0].toString();
    }



}
